{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Majority Element LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #counting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #计数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: majorityElement"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #主要元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>数组中占比超过一半的元素称之为主要元素。给你一个<strong> 整数 </strong>数组，找出其中的主要元素。若没有，返回 <code>-1</code> 。请设计时间复杂度为 <code>O(N)</code> 、空间复杂度为 <code>O(1)</code> 的解决方案。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>[1,2,5,9,5,9,5,5,5]\n",
    "<strong>输出：</strong>5</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>[3,2]\n",
    "<strong>输出：</strong>-1</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>[2,2,1,1,1,2,2]\n",
    "<strong>输出：</strong>2</pre>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-majority-element-lcci](https://leetcode.cn/problems/find-majority-element-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-majority-element-lcci](https://leetcode.cn/problems/find-majority-element-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,2,3]', '[2,2,1,1,1,2,2]', '[1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        num = vote = 0\n",
    "        for x in nums:\n",
    "            if vote == 0:\n",
    "                num = x\n",
    "                vote +=1\n",
    "            else:\n",
    "                if x == num:\n",
    "                    vote += 1\n",
    "                else:\n",
    "                    vote -= 1\n",
    "        if nums.count(num) > len(nums) // 2:\n",
    "            return num\n",
    "        else:\n",
    "            return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        k = len(nums)/2\n",
    "        for n in set(nums):\n",
    "            if nums.count(n) > k:\n",
    "                return n\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        x, count = 0, 0\n",
    "        for i in range(n):\n",
    "            if count == 0:\n",
    "                x = nums[i]\n",
    "            if x == nums[i]:\n",
    "                count += 1\n",
    "            else:\n",
    "                count -= 1\n",
    "        count = 0\n",
    "        for i in range(n):\n",
    "            if x == nums[i]:\n",
    "                count += 1\n",
    "        return x if count > n/2 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        # a = list(set(nums))\n",
    "        # res = -1\n",
    "        # for i in a:\n",
    "        #     if(nums.count(i) > len(nums) / 2):\n",
    "        #         res = i\n",
    "        #         break\n",
    "        \n",
    "        # return res;\n",
    "        res = -1\n",
    "        halflen = int(len(nums) / 2)\n",
    "        nums.sort()\n",
    "        for i in range( 0 , len(nums) - halflen):\n",
    "            if(nums[i] == nums[i + halflen]):\n",
    "                res = nums[i]\n",
    "                break\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        \n",
    "        for i,j in collections.Counter(nums).items():\n",
    "            if j > len(nums) //2:\n",
    "                return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        i, num = 0, nums[0]\n",
    "        while i < len(nums):\n",
    "            count, length = 1, 1\n",
    "            num = nums[i]\n",
    "            while i < len(nums)-1 and count > length // 2:\n",
    "                i, length = i+1, length+1\n",
    "                if nums[i] == num: count += 1\n",
    "            i += 1\n",
    "        count = 0\n",
    "        for n in nums:\n",
    "            if n == num: count += 1\n",
    "        return num if count > len(nums) // 2 else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        dic = {}\n",
    "        for i in nums:\n",
    "            if i in dic:\n",
    "                dic[i] += 1\n",
    "            else:\n",
    "                dic[i] = 1\n",
    "        a = len(nums)//2\n",
    "        for i in dic:\n",
    "            if dic[i] > a:\n",
    "                return i\n",
    "           \n",
    "                \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        for i in set(nums):\n",
    "            if nums.count(i)>len(nums)/2:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        res=defaultdict(int)\n",
    "        for x in nums:\n",
    "            res[x]+=1\n",
    "            if res[x]>n//2:\n",
    "                return x\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "\n",
    "        dic = {}\n",
    "        for i in nums:\n",
    "            if i not in dic:\n",
    "                dic[i] = 1\n",
    "                if dic[i] > len(nums) //2:\n",
    "                    return i \n",
    "            else:\n",
    "                dic[i] += 1\n",
    "                if dic[i] > len(nums) //2:\n",
    "                    return i \n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        #摩尔投票\n",
    "        candidate = -1\n",
    "        count = 0\n",
    "        for num in nums:#找出最多次数的数\n",
    "            if not count:candidate=num\n",
    "            if num == candidate:\n",
    "                count += 1\n",
    "            else:\n",
    "                count -= 1\n",
    "        count = 0\n",
    "        for num in nums:\n",
    "            if num == candidate:\n",
    "                count += 1\n",
    "        if count*2>n: return candidate\n",
    "        else:return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums) -> int:\n",
    "        t = Counter(nums)\n",
    "        x = nums[0]\n",
    "        cnt = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] == x:\n",
    "                cnt+=1\n",
    "            else:\n",
    "                cnt-=1\n",
    "                if cnt <= 0:\n",
    "                    x = nums[i]\n",
    "                    cnt = 1\n",
    "        if cnt>=1 and t[x]>=len(nums)/2:\n",
    "            return x\n",
    "        return -1\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    s = Solution()\n",
    "    s.majorityElement([1,2,3,4,5])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        x,c=-1,0\n",
    "        for n in nums:\n",
    "            if not c:x=n \n",
    "            if x==n:c+=1\n",
    "            else:c-=1\n",
    "        return x if nums.count(x)>len(nums)/2 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        a={}\n",
    "        b=len(nums)//2\n",
    "        for i in nums:\n",
    "            if i not in a:\n",
    "                a[i]=1\n",
    "            if a[i]>b:\n",
    "                return i    \n",
    "            else:\n",
    "                a[i]+=1 \n",
    "        return -1           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        hashmap = defaultdict(int)\n",
    "        for x in nums:\n",
    "            hashmap[x] += 1\n",
    "            if hashmap[x] > n // 2:\n",
    "                return x\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        dict1={}\n",
    "        n=len(nums)//2\n",
    "        for i in nums:\n",
    "            a = str(i)\n",
    "            if a in dict1:\n",
    "                dict1[a] +=1\n",
    "            else:\n",
    "                dict1[a]=1\n",
    "            if dict1[a] > n:\n",
    "                return i\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        # a = list(set(nums))\n",
    "        # res = -1\n",
    "        # for i in a:\n",
    "        #     if(nums.count(i) > len(nums) / 2):\n",
    "        #         res = i\n",
    "        #         break\n",
    "        \n",
    "        # return res;\n",
    "        res = -1\n",
    "        halflen = int(len(nums) / 2)\n",
    "        nums.sort()\n",
    "        for i in range( 0 , len(nums) - halflen):\n",
    "            if(nums[i] == nums[i + halflen]):\n",
    "                res = nums[i]\n",
    "                break\n",
    "\n",
    "        return res;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        a={}\n",
    "        b=len(nums)//2\n",
    "        for i in nums:\n",
    "            if i not in a:\n",
    "                a[i]=1\n",
    "            if a[i]>b:\n",
    "                return i    \n",
    "            else:\n",
    "                a[i]+=1 \n",
    "        return -1           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        a=nums[len(nums)//2]\n",
    "        if nums.count(a)>=(len(nums)//2)+1:\n",
    "            return a\n",
    "        else:\n",
    "            return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        cur_max = None\n",
    "        cur_count = 0\n",
    "\n",
    "        for num in nums:\n",
    "            if cur_count == 0:\n",
    "                cur_max = num\n",
    "            if cur_max == num:\n",
    "                cur_count += 1\n",
    "            else:\n",
    "                cur_count -= 1\n",
    "        \n",
    "        majority_count = 0\n",
    "        \n",
    "        for num in nums:\n",
    "            if num == cur_max:\n",
    "                majority_count += 1\n",
    " \n",
    "        return -1 if majority_count < len(nums)/2 else cur_max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        ds = Counter(nums)\n",
    "        l = len(nums)\n",
    "        for k,v in ds.items():\n",
    "            if v * 2 > l:\n",
    "                return k\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        HashMap = {}\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return nums[0]\n",
    "        # 字典记录每个元素数量\n",
    "        for i in nums:\n",
    "            if i not in HashMap:\n",
    "                HashMap[i] = 1\n",
    "            else:\n",
    "                HashMap[i] += 1\n",
    "        max_Hash = max(zip(HashMap.values(), HashMap.keys()))  # 字典键值对组合，取值最大的\n",
    "        if max_Hash[0] <= n//2:\n",
    "            return -1\n",
    "        else:\n",
    "            return max_Hash[1]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res, count = 0,0\n",
    "        for c in nums:\n",
    "            if count==0:\n",
    "                res = c\n",
    "            if res==c:\n",
    "                count+=1\n",
    "            else:\n",
    "                count-=1\n",
    "        return res if nums.count(res)*2>n else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        c = -1\n",
    "        count = 0\n",
    "        for num in nums:\n",
    "            if count == 0:\n",
    "                c = num\n",
    "            if num == c:\n",
    "                count += 1\n",
    "            else:\n",
    "                count -= 1\n",
    "        count = 0\n",
    "        for num in nums:\n",
    "            if num == c:\n",
    "                count += 1\n",
    "        if count * 2 > len(nums):\n",
    "            return c\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = -1\n",
    "        cnt = 0\n",
    "        for x in nums:\n",
    "            if not cnt:\n",
    "                res = x\n",
    "            if x == res:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                cnt -= 1\n",
    "        return res if cnt and nums.count(res) > n//2 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        x, cnt = -1, 0\n",
    "        for i in nums:\n",
    "            if not cnt:\n",
    "                x = i\n",
    "            if x == i:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                cnt -= 1 \n",
    "        return x if cnt and nums.count(x) > n // 2 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        tmp_count = 0\n",
    "        for i in nums:\n",
    "            if tmp_count == 0:\n",
    "                main_element = i\n",
    "                tmp_count = 1\n",
    "            else:\n",
    "                if i== main_element:\n",
    "                    tmp_count +=1\n",
    "                else:\n",
    "                    tmp_count -=1\n",
    "\n",
    "        if tmp_count and nums.count(main_element) >= len(nums)/2 :\n",
    "            return main_element\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef majorityElement(self, nums: List[int]) -> int:\n",
    "\t\tcounter = collections.Counter(nums)\n",
    "\t\thalf_of_len = len(nums) // 2\n",
    "\t\tfor k in counter:\n",
    "\t\t\tif counter[k] > half_of_len:\n",
    "\t\t\t\treturn k\n",
    "\t\treturn -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        a = len(nums)//2\n",
    "        dic = {}\n",
    "        for n in nums:\n",
    "            if n in dic:\n",
    "                dic[n] = dic[n] + 1\n",
    "            else:\n",
    "                dic[n] = 1\n",
    "\n",
    "            if dic[n] > a:\n",
    "                return n\n",
    "\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res, count = 0,0\n",
    "        for c in nums:\n",
    "            if count==0:\n",
    "                res = c\n",
    "            if res==c:\n",
    "                count+=1\n",
    "            else:\n",
    "                count-=1\n",
    "        return res if nums.count(res)*2>n else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        a = list(set(nums))\n",
    "        result = -1\n",
    "        for i in a:\n",
    "            if(nums.count(i) > len(nums) / 2):\n",
    "                result = i\n",
    "                break\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        dict1={}\n",
    "        for i in nums:\n",
    "            a = str(i)\n",
    "            if a in dict1:\n",
    "                dict1[a] +=1\n",
    "            else:\n",
    "                dict1[a]=1\n",
    "            if dict1[a] > len(nums)/2:\n",
    "                return i\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        lt,rt=0,n//2\n",
    "        for lt in range(n//2):\n",
    "            if nums[rt]==nums[lt]:\n",
    "                for j in range(rt+1,n):\n",
    "                    if nums[j]!=nums[lt]:\n",
    "                        nums[j],nums[rt]=nums[rt],nums[j]\n",
    "                        break\n",
    "                if nums[rt]==nums[lt]:\n",
    "                    return nums[lt]\n",
    "            rt+=1\n",
    "        if rt==n:\n",
    "            return -1\n",
    "        cnt=0\n",
    "        for i in nums:\n",
    "            if i==nums[rt]:\n",
    "                cnt+=1\n",
    "        if cnt>n//2:\n",
    "            return nums[rt]\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        candidate=-1;count=0\n",
    "        for i in nums:\n",
    "            if count==0:\n",
    "                candidate=i\n",
    "            if i==candidate:\n",
    "                count+=1\n",
    "            else:\n",
    "                count-=1\n",
    "        count=0\n",
    "        length=len(nums)\n",
    "        for i in nums:\n",
    "            if candidate==i:\n",
    "                count+=1\n",
    "        return candidate if 2*count>length else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        table = []\n",
    "        for n in nums:\n",
    "            if not n in table:\n",
    "                table.append(n)\n",
    "                if nums.count(n) > len(nums) //2:\n",
    "                    return n\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        x,cnt=-1,0\n",
    "        for i in nums:\n",
    "            if not cnt:\n",
    "                x=i\n",
    "            if x==i:\n",
    "                cnt+=1\n",
    "            else:\n",
    "                cnt-=1\n",
    "        return x if cnt and nums.count(x)>n//2 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        # 摩尔投票\n",
    "        n = len(nums)\n",
    "        res, count = 0,0\n",
    "        for c in nums:\n",
    "            if count==0:\n",
    "                res = c\n",
    "            if res==c:\n",
    "                count+=1\n",
    "            else:\n",
    "                count-=1\n",
    "        return res if nums.count(res)*2>n else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        hash = Counter(nums)\n",
    "        n = ceil(len(nums) / 2)\n",
    "        for k,v in hash.items():\n",
    "            if v >= n:\n",
    "                return k\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        # 摩尔投票过程\n",
    "        candidate = -1\n",
    "        count = 0\n",
    "        for i in nums:\n",
    "            if count == 0:\n",
    "                candidate = i\n",
    "            if candidate == i:\n",
    "                count += 1\n",
    "            else:\n",
    "                count -= 1\n",
    "        \n",
    "        # 验证投票结果\n",
    "        count = 0\n",
    "        for i in nums:\n",
    "            if i == candidate:\n",
    "                count += 1\n",
    "            if count > len(nums) / 2:\n",
    "                return candidate\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        nums1=list(set(nums))\n",
    "        n1=len(nums1)\n",
    "        n2=len(nums)\n",
    "        for i in range(n1):\n",
    "            if nums.count(nums1[i])>n2/2:\n",
    "                return nums1[i]\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        major = None \n",
    "        cnt = 0 \n",
    "        for n in nums:\n",
    "            if cnt == 0:\n",
    "                major = n\n",
    "                cnt += 1 \n",
    "            else:\n",
    "                if n == major:\n",
    "                    cnt += 1 \n",
    "                else:\n",
    "                    cnt -= 1 \n",
    "        if cnt <= 0:\n",
    "            return -1 \n",
    "\n",
    "        cnt = 0\n",
    "        for n in nums:\n",
    "            if n == major:\n",
    "                cnt += 1\n",
    "            if cnt > len(nums) * 0.5:\n",
    "                return major\n",
    "        \n",
    "        return -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        # a = list(set(nums))\n",
    "        # res = -1\n",
    "        # for i in a:\n",
    "        #     if(nums.count(i) > len(nums) / 2):\n",
    "        #         res = i\n",
    "        #         break\n",
    "        \n",
    "        # return res;\n",
    "        res = -1\n",
    "        halflen = int(len(nums) / 2)\n",
    "        nums.sort()\n",
    "        for i in range( 0 , len(nums) - halflen):\n",
    "            if(nums[i] == nums[i + halflen]):\n",
    "                res = nums[i]\n",
    "                break\n",
    "\n",
    "        return res;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        num, count = nums[0], 1\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] == num:\n",
    "                count += 1\n",
    "            elif count > 0:\n",
    "                count -= 1\n",
    "            else:\n",
    "                num = nums[i]\n",
    "                count = 1\n",
    "        freq = 0\n",
    "        for i in range(len(nums)):\n",
    "            if num == nums[i]:\n",
    "                freq += 1\n",
    "        return num if freq >= (len(nums) + 1) // 2 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef majorityElement(self, nums: List[int]) -> int:\n",
    "\t\thalf_of_len = len(nums) / 2\n",
    "\t\tdic = {}\n",
    "\t\tfor num in nums:\n",
    "\t\t\tif num in dic:\n",
    "\t\t\t\tdic[num] += 1\n",
    "\t\t\telse:\n",
    "\t\t\t\tdic[num] = 1\n",
    "\t\t\tif dic[num] > half_of_len:\n",
    "\t\t\t\treturn num\n",
    "\t\treturn -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        dic={}\n",
    "        for i in nums:\n",
    "            if i in dic:dic[i] +=1\n",
    "            else:dic[i] = 1\n",
    "\n",
    "        my_n = -1\n",
    "        mode = -1\n",
    "        for value,N in dic.items():\n",
    "            if  N > my_n:\n",
    "                mode = value\n",
    "                my_n = N\n",
    "        \n",
    "        if dic[mode] > len(nums)/2:\n",
    "            return mode\n",
    "        else:\n",
    "            return -1\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        a=len(nums)/2\n",
    "        b=set(nums)\n",
    "        for i in b:\n",
    "            x=nums.count(i)\n",
    "            if x>a:\n",
    "                return i\n",
    "            else:\n",
    "                continue\n",
    "        return -1\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        for i in set(nums):\n",
    "            if nums.count(i) > len(nums) / 2:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        cur_max = None\n",
    "        cur_count = 0\n",
    "\n",
    "        for num in nums:\n",
    "            if cur_max == num:\n",
    "                cur_count += 1\n",
    "            else:\n",
    "                if cur_count == 0:\n",
    "                    cur_count += 1\n",
    "                    cur_max = num\n",
    "                else:\n",
    "                    cur_count -= 1\n",
    "        \n",
    "        majority_count = 0\n",
    "        for num in nums:\n",
    "            if num == cur_max:\n",
    "                majority_count += 1\n",
    " \n",
    "        return -1 if majority_count < len(nums)/2 else cur_max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res, count = 0,0\n",
    "        for c in nums:\n",
    "            if count==0:\n",
    "                res = c\n",
    "            if res==c:\n",
    "                count+=1\n",
    "            else:\n",
    "                count-=1\n",
    "        return res if nums.count(res)*2>n else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "\n",
    "        count = collections.Counter(nums)\n",
    "        n = len(nums)\n",
    "        for key, val in count.items():\n",
    "            if val > (n / 2):\n",
    "                return key\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        count = 0\n",
    "        res = None\n",
    "        for num in nums:\n",
    "            if num == res:\n",
    "                count += 1\n",
    "            else:\n",
    "                if count == 0:\n",
    "                    res = num\n",
    "                    count += 1\n",
    "                else:\n",
    "                    count -= 1\n",
    "        count = len(nums) // 2 + 1\n",
    "        for num in nums:\n",
    "            if num == res:\n",
    "                count -= 1\n",
    "        return res if count <= 0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        candi = -1\n",
    "        count = 0\n",
    "        for x in nums:\n",
    "            if count == 0:\n",
    "                candi = x\n",
    "            if candi == x:\n",
    "                count += 1\n",
    "            else:\n",
    "                count -= 1\n",
    "        \n",
    "        candi_count = 0\n",
    "        for x in nums:\n",
    "            if x == candi:\n",
    "                candi_count += 1\n",
    "        \n",
    "        if candi_count * 2 > len(nums):\n",
    "            return candi\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums_counter = Counter(nums)\n",
    "        nums_dict = dict(nums_counter)\n",
    "        for k,v in nums_dict.items():\n",
    "            if v > n // 2:\n",
    "                return k\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef majorityElement(self, nums: List[int]) -> int:\n",
    "\t\thalf_of_len = len(nums) / 2\n",
    "\t\tdic = {}\n",
    "\t\tfor num in nums:\n",
    "\t\t\tif num in dic:\n",
    "\t\t\t\tdic[num] += 1\n",
    "\t\t\telse:\n",
    "\t\t\t\tdic[num] = 1\n",
    "\t\t\tif dic[num] > half_of_len:\n",
    "\t\t\t\treturn num\n",
    "\t\treturn -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        cur_max = None\n",
    "        cur_count = 0\n",
    "\n",
    "        for num in nums:\n",
    "            if cur_max == num:\n",
    "                cur_count += 1\n",
    "            else:\n",
    "                if cur_count != 0:\n",
    "                    cur_count -= 1\n",
    "                else:\n",
    "                    cur_count += 1\n",
    "                    cur_max = num\n",
    "                    \n",
    "        \n",
    "        majority_count = 0\n",
    "\n",
    "        for num in nums:\n",
    "            if num == cur_max:\n",
    "                majority_count += 1\n",
    " \n",
    "        return -1 if majority_count < len(nums)/2 else cur_max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        len_nums = len(nums)\n",
    "        if len_nums % 2 != 0:\n",
    "            len_nums1 = (len_nums - 1) / 2\n",
    "        else:\n",
    "            len_nums1 = len_nums / 2\n",
    "        len_nums1 = int(len_nums1)\n",
    "        nums = sorted(nums)\n",
    "        if nums.count(nums[len_nums1]) > len_nums1:\n",
    "            return nums[len_nums1]\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        hashmap = defaultdict(int)\n",
    "        for x in nums:\n",
    "            hashmap[x] += 1\n",
    "            if hashmap[x] > n // 2:\n",
    "                return x\n",
    "        return -1\n",
    "\n",
    "# 作者：宫水三叶\n",
    "# 链接：https://leetcode.cn/problems/find-majority-element-lcci/solutions/866179/gong-shui-san-xie-yi-ti-shuang-jie-ha-xi-zkht/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        # c = Counter(nums)\n",
    "        # for i in c:\n",
    "        #     if c[i] > len(nums) / 2:\n",
    "        #         return i\n",
    "        # return -1\n",
    "\n",
    "        # ---------------------\n",
    "        # if not nums:\n",
    "        #     return -1\n",
    "        # candidate = count = 0\n",
    "        # for num in nums:\n",
    "        #     if count == 0:\n",
    "        #         candidate = num \n",
    "        #     if num == candidate:\n",
    "        #         count += 1\n",
    "        #     else:\n",
    "        #         count -= 1\n",
    "        # count = 0\n",
    "        # for num in nums:\n",
    "        #     if num == candidate:\n",
    "        #         count += 1\n",
    "        # return candidate if count > len(nums) / 2 else -1\n",
    "\n",
    "        # ---------------------\n",
    "        # if not nums:\n",
    "        #     return -1\n",
    "        # candidate = count = 0\n",
    "        # for num in nums:\n",
    "        #     if count == 0:\n",
    "        #         candidate = num \n",
    "        #     if num == candidate:\n",
    "        #         count += 1\n",
    "        #     else:\n",
    "        #         count -= 1\n",
    "        # return candidate if nums.count(candidate) > len(nums) / 2 else -1\n",
    "\n",
    "        # -------------------------------\n",
    "        res = -1\n",
    "        halflen = int(len(nums) / 2)\n",
    "        nums.sort()\n",
    "        for i in range( 0 , len(nums) - halflen):\n",
    "            if(nums[i] == nums[i + halflen]):\n",
    "                res = nums[i]\n",
    "                break\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        hashmap = defaultdict(int)\n",
    "        for x in nums:\n",
    "            hashmap[x] += 1\n",
    "            if hashmap[x] > n // 2:\n",
    "                return x\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef majorityElement(self, nums: List[int]) -> int:\n",
    "\t\thalf_of_len = len(nums) / 2\n",
    "\t\tdic = {}\n",
    "\t\tfor num in nums:\n",
    "\t\t\tif num in dic:\n",
    "\t\t\t\tdic[num] += 1\n",
    "\t\t\telse:\n",
    "\t\t\t\tdic[num] = 1\n",
    "\t\t\tif dic[num] > half_of_len:\n",
    "\t\t\t\treturn num\n",
    "\t\treturn -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        now, cnt = nums[0], 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if cnt == 0:\n",
    "                now = x\n",
    "            if now == x:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                cnt -= 1\n",
    "        return now if nums.count(now) > len(nums) // 2 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        hashmap = defaultdict(int)\n",
    "        for x in nums:\n",
    "            hashmap[x] += 1\n",
    "            if hashmap[x] > n//2:\n",
    "                return x\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        x ,cnt = -1, 0\n",
    "\n",
    "        for i in nums:\n",
    "            if not cnt:\n",
    "                x = i\n",
    "            if x == i:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                cnt -= 1\n",
    "        \n",
    "        return x if cnt and nums.count(x) > n//2 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: list[int]) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "        half_len = len(nums) // 2\n",
    "        nums.sort()\n",
    "        for i in range(half_len + 1):\n",
    "            if nums[i + half_len] == nums[i]:\n",
    "                return nums[i]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        cnt, mj = 1, nums[0]\n",
    "        n = len(nums)\n",
    "        for i in range(1, n):\n",
    "            x = nums[i]\n",
    "            if mj != x:\n",
    "                cnt -= 1\n",
    "                if cnt == 0:\n",
    "                    mj = x\n",
    "                    cnt = 1\n",
    "            else:\n",
    "                cnt += 1\n",
    "        if sum(1 for x in nums if x == mj) >= (n + 1)//2:\n",
    "            return mj\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        # 摩尔投票\n",
    "        n = len(nums)\n",
    "        res, count = 0,0\n",
    "        for c in nums:\n",
    "            if count==0:\n",
    "                res = c\n",
    "            if res==c:\n",
    "                count+=1\n",
    "            else:\n",
    "                count-=1\n",
    "        return res if nums.count(res)*2>n else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        major = None \n",
    "        cnt = 0 \n",
    "        for n in nums:\n",
    "            if cnt == 0:\n",
    "                major = n\n",
    "                cnt += 1 \n",
    "            else:\n",
    "                if n == major:\n",
    "                    cnt += 1 \n",
    "                else:\n",
    "                    cnt -= 1 \n",
    "        if cnt <= 0:\n",
    "            return -1 \n",
    "\n",
    "        cnt = 0\n",
    "        for n in nums:\n",
    "            if n == major:\n",
    "                cnt += 1\n",
    "            if cnt > len(nums) * 0.5:\n",
    "                return major\n",
    "        \n",
    "        return -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res, count = 0,0\n",
    "        for c in nums:\n",
    "            if count==0:\n",
    "                res = c\n",
    "            if res==c:\n",
    "                count+=1\n",
    "            else:\n",
    "                count-=1\n",
    "        print(res)\n",
    "        return res if nums.count(res)*2>n else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        x, cnt = -1, 0\n",
    "        for num in nums:\n",
    "            if not cnt:\n",
    "                x = num\n",
    "            if x == num:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                cnt -= 1\n",
    "        return x if cnt and nums.count(x) > n // 2 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        if len(nums) != 1:\n",
    "            nums1 = set(nums)\n",
    "            for i in nums1:\n",
    "                if nums.count(i) > len(nums) // 2:\n",
    "                    return i\n",
    "        else:\n",
    "            return nums[0]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return -1\n",
    "        num, cnt = None, 0\n",
    "        for i in nums:\n",
    "            if cnt:\n",
    "                if i!=num:\n",
    "                    cnt-=1\n",
    "                else:\n",
    "                    cnt+=1\n",
    "            else:\n",
    "                num, cnt = i, 1\n",
    "        return num if nums.count(num)>len(nums)//2 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        res = -1\n",
    "        cnt = 0\n",
    "        for i in nums:\n",
    "            if cnt == 0:\n",
    "                res = i\n",
    "            if i == res:\n",
    "                cnt+=1\n",
    "            else :\n",
    "                cnt-=1\n",
    "        if cnt < 1:\n",
    "            return -1\n",
    "        if nums.count(res) <= len(nums)//2 :\n",
    "            return -1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        c = Counter(nums)\n",
    "        s = sorted(c.items(), key=lambda x: x[1], reverse=True)\n",
    "        if s[0][1] * 2 > len(nums):\n",
    "            return s[0][0]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        # c = Counter(nums)\n",
    "        # for i in c:\n",
    "        #     if c[i] > len(nums) / 2:\n",
    "        #         return i\n",
    "        # return -1\n",
    "\n",
    "        # ---------------------\n",
    "        if not nums:\n",
    "            return -1\n",
    "        candidate = count = 0\n",
    "        for num in nums:\n",
    "            if count == 0:\n",
    "                candidate = num \n",
    "            if num == candidate:\n",
    "                count += 1\n",
    "            else:\n",
    "                count -= 1\n",
    "        count = 0\n",
    "        for num in nums:\n",
    "            if num == candidate:\n",
    "                count += 1\n",
    "        return candidate if count > len(nums) / 2 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        for i in set(nums):\n",
    "            if nums.count(i) > int(len(nums)/2):\n",
    "                return i\n",
    "          \n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        out_dir = {}\n",
    "        if len(nums) != 1:\n",
    "            for i in nums:\n",
    "                if i in out_dir:\n",
    "                    out_dir[i] += 1\n",
    "                    if out_dir[i] > len(nums)//2:\n",
    "                        return i\n",
    "                else:\n",
    "                    out_dir[i] = 1\n",
    "        else:\n",
    "            return nums[0]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "\n",
    "        # 摩尔投票法\n",
    "        # 原理：类似诸侯争霸拼消耗，假设你的人口超过总的一半以上，\n",
    "        # 那么只要你的每个人出去能消耗掉对方一个人，那么最终剩下的一定是你的人\n",
    "\n",
    "\n",
    "        count = 0\n",
    "        candidate = None\n",
    "\n",
    "        for num in nums:\n",
    "            if count == 0: # 无阵营占据多数位，当前阵营企图上位\n",
    "                candidate = num\n",
    "                count = 1\n",
    "            elif num == candidate: # 遇到当前阵营人，累计一个人数\n",
    "                count += 1\n",
    "            else: # 遇到非当前阵营人，进行一次消耗\n",
    "                count -= 1\n",
    "\n",
    "\n",
    "        # 本题和169题不同（https://leetcode.cn/problems/majority-element/?envType=list&envId=v4CIqfZB）\n",
    "        # 重要！！！ 本题不保证一定存在众数，所以得到结果还要验证一下：\n",
    "\n",
    "        cnt = 0\n",
    "        for num in nums:\n",
    "            if num == candidate:\n",
    "                cnt += 1\n",
    "        \n",
    "        if cnt > len(nums)/2:\n",
    "            return candidate\n",
    "        else:\n",
    "            return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        # a = list(set(nums))\n",
    "        # res = -1\n",
    "        # for i in a:\n",
    "        #     if(nums.count(i) > len(nums) / 2):\n",
    "        #         res = i\n",
    "        #         break\n",
    "        \n",
    "        # return res;\n",
    "        res = -1\n",
    "        halflen = int(len(nums) / 2)\n",
    "        nums.sort()\n",
    "        for i in range( 0 , len(nums) - halflen):\n",
    "            if(nums[i] == nums[i + halflen]):\n",
    "                res = nums[i]\n",
    "                break\n",
    "\n",
    "        return res;"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
